﻿function Node(val) {
    this.value = val;
    this.right = null;
    this.left = null;
};

function BinaryTree() {
    this.root = null;
    this.Add = function (val) {
        if (this.root == null) {
            this.root = new Node(val);
        }
        else {
            AddNode(this.root, val);
        }
    };
    this.Delete = function (val) {
        if (this.root != null && this.root.value == val)
            this.root = null;
        else {
            DeleteNode(this.root, this.root, val);
        }
    };
    this.Reverse = function () {
        Reverse(this.root);
    }
    var h;
    this.Height = function () {
        Height(this.root);
    }
    function Height(node) {
        h = 0;
        if (node != null) {
            h = Math.max(Height(node.left), Height(node.right)) + 1;
        }

    }

    function AddNode(node, val) {
        if (node.right == null && val >= node.value)
            node.right = new Node(val);
        else if (node.left == null && val < node.value)
            node.left = new Node(val);
        else {
            if (val >= node.value)
                AddNode(node.right, val);
            else
                AddNode(node.left, val);
        }
    }

    function DeleteNode(root, node, val) {
        if (val > node.value) {
            DeleteNode(root, node.right, val);
        }
        else if (val < node.value) {
            DeleteNode(root, node.left, val);
        }
        else {
            if (node.left == null && node.right == null) {
                if (root.value == val)
                    root = null;
                else
                    RemoveLinkNode(root, node.value);
            }
            else if (node.left == null) {
                node.value = node.right.value;
                node.left = node.right.left;
                node.right = node.right.right;
            }
            else if (node.right == null) {
                node.value = node.left.value;
                node.right = node.left.right;
                node.left = node.left.left;
            }
            else {
                var leftInRightNode = FindLeftInRight(node.right);
                node.value = leftInRightNode.value;
                if (node.right.value == leftInRightNode.value) {
                    node.right = null;
                }
                else {
                    RemoveLeftInRight(node.right, leftInRightNode.value);
                }
            }
        }
    }

    function RemoveLinkNode(node, val) {
        if (node.left != null) {
            if (node.left.value == val) {
                node.left = null;
            }
            else {
                RemoveLinkNode(node.left, val);
            }
        }
        if (node.right != null) {
            if (node.right.value == val) {
                node.right = null;
            }
            else {
                RemoveLinkNode(node.right, val);
            }
        }
    }

    function FindLeftInRight(node) {
        var returnValue;
        if (node.left == null) {
            returnValue = node;
        }
        else {
            returnValue = FindLeftInRight(node.left);
        }
        return returnValue;
    }

    function RemoveLeftInRight(node, val) {
        if (node.left != null) {
            if (node.left.value == val) {
                node.left = null;
            }
            else {
                RemoveLeftInRight(node.left, val);
            }
        }
    }

    function Reverse(node) {
        if (node != null) {
                temp = node.left;
                node.left = node.right;
                node.right = temp;
                Reverse(node.left);
                Reverse(node.right);
            }
            
        }
   
}